from typing import List


class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 三指针
        # 左边，当前，右边
        left, cnt, right = 0, 0, len(nums) - 1
        while cnt <= right:
            if nums[cnt] == 0:
                # 交换 第一个 和 cnt的位置
                nums[left], nums[cnt] = nums[cnt], nums[left]
                left += 1
                cnt += 1
            elif nums[cnt] == 2:
                # 交换 最后一个 和 cnt的位置
                nums[right], nums[cnt] = nums[cnt], nums[right]
                right -= 1
                # cnt 不做处理 因为交换过来的数字还是判断
            else:
                cnt += 1

